package com.problem.binarySearch;

/**
 * @author yyh
 * @date 2024年11月11日 下午8:09
 * <a href="https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-interview-150">...</a>
 */
public class SearchInsert {

    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * <p>
     * 请必须使用时间复杂度为 O(log n) 的算法。
     */


    public int searchInsert(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        int index = (left + right) / 2;

        while (right >= left) {
            if (nums[index] == target) {
                return index;
            }

            if (nums[index] > target) {
                right = index - 1;
            } else {
                left = index + 1;
            }
            index = (left + right) / 2;
        }

        int[] newNums = new int[nums.length + 1];
        if (index == 0 && nums[0] > target) {
            newNums[0] = target;
            System.arraycopy(nums, 0, newNums, 1, nums.length);
            return index;
        }

        System.arraycopy(nums, 0, newNums, 0, index + 1);
        newNums[index + 1] = target;
        System.arraycopy(nums, index + 1, newNums, index + 2, nums.length - 1 - index);

        for (int i : newNums) {
            System.out.print(i + " ");
        }
        System.out.println();

        return index + 1;

    }

    public static void main(String[] args) {
        SearchInsert s = new SearchInsert();

        System.out.println(s.searchInsert(new int[]{1, 3, 5, 6}, 5));
        System.out.println(s.searchInsert(new int[]{1, 3, 5, 6}, 2));
        System.out.println(s.searchInsert(new int[]{1, 3, 5, 6}, 7));
        System.out.println(s.searchInsert(new int[]{1, 3, 5, 6}, 0));

    }

}
